/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/shortest-duplicate-subarray
   @Language: C++
   @Datetime: 19-03-14 09:50
   */

// Time 510ms, Space 38MB
class Solution {
public:
	/**
	 * @param arr: The array you should find shortest subarray length which has duplicate elements.
	 * @return: Return the shortest subarray length which has duplicate elements.
	 */
	int getLength(vector<int> &arr) {
		// Write your code here.
		unordered_map<int,int> hash;    // num,index
		unordered_map<int,int>::iterator it;
		int min=arr.size()+1;
		for(int i=0; i<arr.size(); ++i){
			it = hash.find(arr[i]);
			if (it!=hash.end()){
				int len=i-(it->second)+1;
				min=(min>len?len:min);
				it->second=i;
				if (min==2) return 2;
			}
			else hash[arr[i]]=i;
		}
		return min==arr.size()+1 ? -1:min;
	}
};
